/*
 * @: 
 * @version: 1.0
 * @Author: ziwei
 * @Date: 2022-01-11 22:26:18
 * @LastEditors: ziwei
 * @LastEditTime: 2022-01-11 22:38:49
 */
/**
 * @param {number} k
 * @param {number[]} nums
 */
var KthLargest = function (k, nums) {
    this.size = k;
    this.minHeap = new MinHeap()
    for (let item of nums) {
        this.add(item);
    }
};

/** 
 * @param {number} val
 * @return {number}
 */
KthLargest.prototype.add = function (val) {
    if (this.minHeap.size() < this.size) {
        this.minHeap.offer(val);
    } else if (val > this.minHeap.peek()) {
        this.minHeap.poll()
        this.minHeap.offer(val)
    }
    console.log(this.minHeap.peek());
    return this.minHeap.peek();
};

/**
 * Your KthLargest object will be instantiated and called as such:
 * var obj = new KthLargest(k, nums)
 * var param_1 = obj.add(val)
 */
class MinHeap {
    constructor(data = []) {
        this.data = data
        this.comparator = (a, b) => a - b;
        this.heapify()
    }
    heapify() {
        if (this.size() < 2) return;
        for (let i = 1; i < this.size(); i++) {
            this.bubbleUp(i)
        }
    }
    //弹出顶部
    poll() {
        if (this.size() === 0) {
            return null;
        }
        const result = this.data[0];
        const last = this.data.pop();
        if (this.size() !== 0) {
            // 最末尾元素放到堆顶
            this.data[0] = last;
            // 向下调整直至放到合适位置
            this.bubbleDown(0);
        }
        return result;
    }
    //offer 压入
    offer(val) {
        this.data.push(val)
        this.bubbleUp(this.size() - 1)
    }
    //向下
    bubbleDown(index) {
        const lastIndex = this.size() - 1;
        while (true) {
            // 获得要调整的节点的左子节点和右子节点的索引
            const leftIndex = index * 2 + 1;
            const rightIndex = index * 2 + 2;
            let findIndex = index;
            // 如果左/右子节点的值小于当前要调整的节点的值
            if (
                leftIndex <= lastIndex &&
                this.comparator(this.data[leftIndex], this.data[findIndex]) < 0
            ) {
                findIndex = leftIndex;
            }
            if (
                rightIndex <= lastIndex &&
                this.comparator(this.data[rightIndex], this.data[findIndex]) < 0
            ) {
                findIndex = rightIndex;
            }
            // 则要交换
            if (index !== findIndex) {
                this.swap(index, findIndex);
                index = findIndex;
            } else {
                break;
            }
        }
    }
    //向上
    bubbleUp(index) {
        while (index > 0) {
            // 获得父节点索引
            const parentIndex = (index - 1) >> 1;
            console.log("+++parentIndex", parentIndex);
            // 如果要调整的节点比父节点的值还要小，就需要一直往上冒
            if (this.comparator(this.data[index], this.data[parentIndex]) < 0) {
                // 交换位置往上冒
                this.swap(index, parentIndex);
                console.log("+++index", index);
                index = parentIndex;
            } else {
                break;
            }
        }
    }

    peek() {
        if (this.size() == 0) return
        return this.data[0]
    }

    //交换
    swap(index1, index2) {
        [this.data[index1], this.data[index2]] = [
            this.data[index2],
            this.data[index1],
        ];
    }
    size() {
        return this.data.length
    }
}

let a = new KthLargest(2, [0])
a.add(-1)
a.add(1)
a.add(-2)
a.add(-4)
a.add(-3)